package org.example.sort;

//归并排序算法
public class MergeSort {
    public static void main(String[] args){
        Integer[] arr = {10,15,97,15,64,75,0,23,78,62,197,2};
        sort(arr);
        //循环遍历输出结果
        for (int j = 0; j < arr.length; j++) {
            System.out.print(arr[j]+" ");
        }

    }

    //定义排序所需要的辅助数组
    //Comparable[]可以表示所有实现了这个接口的数据类型的数组
    private static Comparable[] assist;

    //将数组中的两个元素交换顺序
    private static void exch(Comparable[] arr,int i,int j){
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //对数组中的数据进行归并排序
    public static void sort(Comparable[] arr){
        //初始化辅助数组
        assist = new Comparable[arr.length];
        //定义lo变量和hi变量记录数组中最小的索引和最大的索引
        int lo=0,hi=arr.length-1;
        //调用sort方法完成数组中从lo到hi的元素排序
        sort (arr,lo,hi);
    }

    //对数组中的从lo到hi的数据进行排序
    public static void sort(Comparable[] arr,int lo,int hi){
        //安全性校验
        if (lo>=hi) return;
        //对数据分为两个组
        int mid=lo+(hi-lo)/2;
        //分别对每一组数据排序
        //递归调用
        sort(arr,lo,mid);//前半段
        sort(arr,mid+1,hi);//后半段
        //把两个组中的数据归并
        merge(arr,lo,mid,hi);
    }

    //将两个数组合并 lo与mid是一组，mid和hi是一组进行合并
    public  static void merge(Comparable[] arr,int lo,int mid,int hi){
        //现在左边数组和右边数组都是有序的状态
        //定义三个指针分别指向左边数组和右边数组的第一个数据还有辅助数组的第一个索引处
        int p1=lo,p2=mid+1;
        int p3=lo;
        //分别比较两边谁小，小的放到辅助数组中，并移动指针，还要移动辅助数组的指针
        while (p1<=mid &&p2<=hi){
            if (arr[p1].compareTo(arr[p2])<=0){
                assist[p3]=arr[p1];
                p1++;
            }else {
                assist[p3]=arr[p2];
                p2++;
            }
            p3++;
        }
        //如果p1没有走完，则顺序把p1的剩下的元素放到辅助数组中
        while (p1<=mid){
            assist[p3]=arr[p1];
            p3++;
            p1++;
        }
        //如果p2没有走完，则顺序把p2的剩下的元素放到辅助数组中
        while (p2<=hi){
            assist[p3]=arr[p2];
            p3++;
            p2++;
        }
        //将辅助数组放回原数组的指定位置
        for (int i=lo;i<=hi;i++){
            arr[i]=assist[i];
        }
    }
}
